package PersonStu.sanqi;

import java.util.*;

/**
 * @Author: Dijah
 * @Date: 2022/12/8 15:37
 * @Desc: 最短单词路径
 * 描述：
 * 给定两个单词找到从 beginWord到 endWord 的最短转换序列的长度
 * 1、每次转换只能改变一个字母。
 * 2、转换过程中的中间单词必须是字典中的单词。
 * 要求：
 * 如果不存在这样的转换序列，返回 0。
 * 所有单词具有相同的长度。
 * 所有单词只由小写字母组成。
 * 字典中不存在重复的单词。
 * 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
 */
public class code_11_minWordsPaths {

    public static List<List<String>> findMinPaths(String start,String end,List<String> list){
        list.add(start);
        //找到所有的邻居表，返回的是HashMap.key:单词，value:相邻单词的集合
        HashMap<String, ArrayList<String>> nexts = getNexts(list);
        //距离=>从start到相邻单词的最短距离
        HashMap<String,Integer> distance = getDistances(start,nexts);
        //
        LinkedList<String> pathList = new LinkedList<>();
        //返回的结果
        List<List<String>> res = new ArrayList<>();
        //找到最短的
        getShortestPaths(start,end,nexts,distance,pathList,res);
        return res;
    }


    private static HashMap<String, ArrayList<String>> getNexts(List<String> words) {
        //Word放到set中
        Set<String> dict =  new HashSet<>(words);
        HashMap<String,ArrayList<String>> nexts = new HashMap<>();
        for (int i = 0; i < words.size(); i++) {
            nexts.put(words.get(i), getNext(words.get(i), dict));
        }
        return nexts;
    }

    /**
     * 获取相邻单词
     * @param word
     * @param dict
     * @return
     */
    private static ArrayList<String> getNext(String word, Set<String> dict) {
        ArrayList<String> res = new ArrayList<>();
        char[] chs = word.toCharArray();
        for(char cur = 'a'; cur <= 'z'; cur++){
            for (int i = 0; i < chs.length; i++) {
                if(chs[i] != cur){
                    //当前位置的字母不等于chs中的
                    char temp = chs[i];
                    chs[i] = cur;
                    if(dict.contains(String.valueOf(chs))){
                        res.add(String.valueOf(chs));
                    }
                    chs[i] = temp;
                }
            }
        }
        return res;
    }

    private static HashMap<String, Integer> getDistances(String start, HashMap<String, ArrayList<String>> nexts) {
        HashMap<String,Integer> distances = new HashMap<>();
        distances.put(start,0);
        Queue<String> queue = new LinkedList<String>();
        queue.add(start);
        HashSet<String> set = new HashSet<>();
        set.add(start);
        while (!queue.isEmpty()){
            String cur = queue.poll();
            for (String next : nexts.get(cur)) {
                if(!set.contains(next)){
                    //判断不包含是为了，重复的数据，不记录重复的
                    distances.put(next,distances.get(cur) + 1);
                    queue.add(next);
                    set.add(next);
                }
            }
        }
        return distances;
    }

    /**
     *
     * @param cur 当前位置
     * @param to 要去哪里
     * @param nexts 邻居表
     * @param distance 最短距离表
     * @param pathList 沿途走过的路
     * @param res 收集所有的最短路径
     */
    private static void getShortestPaths(String cur,
                                         String to,
                                         HashMap<String, ArrayList<String>> nexts,
                                         HashMap<String, Integer> distance,
                                         LinkedList<String> pathList,
                                         List<List<String>> res) {
        //当前的位置肯定是要追加上的
        pathList.addLast(cur);
        if(to.equals(cur)){
            res.add(new LinkedList<String>(pathList));
        }else {
            for (String next : nexts.get(cur)) {
                //因为每次只能个改变一个字母，所以   当前的位置+1 = next；
                if(distance.get(next) == distance.get(cur) + 1){
                    getShortestPaths(next,to,nexts,distance,pathList,res);
                }
            }
        }
        //最后一个出队
        pathList.pollLast();

    }

    public static void main(String[] args) {
        String start = "abc";
        String end = "cab";
        String[] test = { "abc", "cab", "acc", "cbc", "ccc", "cac", "cbb", "aab", "abb" };
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < test.length; i++) {
            list.add(test[i]);
        }
        List<List<String>> res = findMinPaths(start, end, list);
        for (List<String> obj : res) {
            for (String str : obj) {
                System.out.print(str + " -> ");
            }
            System.out.println();
        }
    }
}
